package com.azure.code.dfs.island;

/**
 * 统计子岛屿 https://leetcode.cn/problems/count-sub-islands/
 *  0 海水 1 陆地
 *  如何判断子岛屿？
 *  当岛屿B中所有的陆地在岛屿A中的也是陆地的时候，岛屿B是岛屿A的子岛屿，
 *  反过来说，如果岛屿B中存在一片陆地，在岛屿A的对应位置是海水，那么B就不是岛屿A的子岛屿
 */
public class Island_1905 {

    public int countSubIslands(int[][] grid1, int[][] grid2) {
        int m = grid1.length,n = grid1[0].length;
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(grid1[i][j]==0&&grid2[i][j]==1) {
                    // 这个岛屿肯定不是子岛屿
                    dfs(grid2,i,j);
                }
            }
        }
        // 现在grid2中剩下的岛屿都是子岛屿，计算岛屿的数量
        int res = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if(grid2[i][j]==1){
                    res++;
                    dfs(grid2,i,j);
                }
            }
        }
        return res;
    }

    private void dfs(int[][] grid,int i, int j) {
        int m = grid.length,n = grid[0].length;
        if(i < 0 || j < 0 || i>=m || j>=n) return;
        if(grid[i][j] == 0) return;
        grid[i][j] = 0;
        dfs(grid,i,j+1);
        dfs(grid,i+1,j);
        dfs(grid,i-1,j);
        dfs(grid,i,j-1);
    }
}
